package com.linchong.dynamicprogramming.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-26 14:24
 * @Description: Backpack$背包问题-lintCode92
 *
 * 给定n个物品，重量分别是正整数A0,A1,A2,...,An-1,价值分别是V0,V1,...,Vn-1
 * 一个背包最大承重是正整数M
 * 每种物品都有无穷多个
 * 最多能带走多大价值的物品
 *
 * eg:
 *  输入：4个物品，重量为2,3,5,7,价值是1,5,2,4,,最大承重是10
 *  输出：15,(3x物品一,3*3=9，重量9，3*5=15,价值15)
 *
 *
 * !!! 背包问题，重量一定放在数据下标中
 *
 * 【解析】
 *  背包最大承重是M,每个装物品的方案的总重量都是0到M
 *  如果对于每个总重量，我们能知道对应的最大价值是多少，就可以知道答案
 *
 *  step1:确定状态
 *
 */
public class BackpackIII {


	/**
	 *
	 * @param item 物品
	 * @param m 最大承重
	 * @param v 价值
	 * @return
	 */
	int backPack(int[] item,int m,int[] v){



		return 0;
	}

	public static void main(String[] args) {
		int[] item = {2,3,5,7};
		int[] value = {1,2,4,7};
		int m = 10;
		BackpackIII instance = new BackpackIII();
		System.out.println(instance.backPack(item,m,value));
	}

}
